package cg.studio.practise.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.junit.Before;
import org.junit.Test;

import cg.studio.model.RandomTree;

/**
 * Provide suggest when user input part of string
 * 
 * @author brightchen
 *
 */
public class Suggester
{
  @Before
  public void buildTree()
  {
    addString( "apple" );
    addString( "able" );
    addString( "ant" );
    addString( "alpha" );
    addString( "angle" );
    addString( "angla" );
  }
  
  @Test
  public void testSuggest()
  {
    testSuggest( "ang" );
    testSuggest( "an" );
    testSuggest( "a" );
  }
  
  public void testSuggest( String str )
  {
    String[] words = suggest( str );
    System.out.print( str + ": " );
    if( words != null )
    {
      for( String word : words )
      {
        System.out.print( word + "; " );
      }
    }
    System.out.println();
    
  }
  
  //use a tree with empty value as the root
  private RandomTree<Character, String> root = new RandomTree<Character, String>( "" );
  
  /**
   * add a string in the tree
   * @param str
   */
  public void addString( String str )
  {
    char[] chars = str.toCharArray();
    RandomTree<Character, String> parent = root;
    
    for( char theChar : chars )
    {
      RandomTree<Character, String> tree = parent.getSubTree( theChar );
      if( tree == null )
      {
        tree = new RandomTree<Character, String>( parent.getValue()+theChar );
        parent.addSubTree( theChar, tree );
      }
      parent = tree;
    }
  }
  
  public String[] suggest( String str )
  {
    char[] chars = str.toCharArray();
    RandomTree<Character, String> parent = root;
    
    for( char theChar : chars )
    {
      parent = parent.getSubTree( theChar );
      if( parent == null )
        break;
    }
    if( parent == null )
      return null;
    
    List< String > values = parent.getAllLeafValues( new ArrayList<String>() );
    return values.toArray( new String[]{} );
  }
}
